#ifndef     __PRIORITY_LIST_H
#define     __PRIORITY_LIST_H

#include <stdint.h>

namespace utils {

template <typename EleType, typename UIntType>
struct Node {

    using ThisType = Node<EleType, UIntType>;

    EleType ele;
    UIntType priorityValue;
    ThisType *prev = nullptr;
    ThisType *next = nullptr;

    void insert(ThisType *node) {
        node->removeSelf();
        node->next = next;
        if (next != nullptr) {
            next->prev = node;
        }
        next = node;
        node->prev = this;
    }

    void removeSelf() {
        if (prev == nullptr) {
            return;
        }
        ThisType *p = prev;
        p->next = next;
        if (next != nullptr) {
            next->prev = p;
        }
        prev = nullptr;
        next = nullptr;
    }
};

template <typename EleType, typename UIntType> 
class PriorityList {
public:
    using NodeType = Node<EleType, UIntType>;

    inline NodeType* front() {
        return m_head.next;
    }

    inline bool empty() const {
        return m_head.next == nullptr;
    }

    void removeByEle(const EleType &ele) {
        NodeType *node = m_head.next;
        for (; node != nullptr; node = node->next) {
            if (node->ele == ele) {
                node->removeSelf();
                return;
            }
        }
    }

    uint32_t size() const {
        NodeType *node = m_head.next;
        uint32_t size = 0;
        for (; node != nullptr; node = node->next) {
            size ++;
        }
        return size;
    }

    void insert(NodeType *node) {
        NodeType *prev = &m_head;
        NodeType *next = m_head.next;
        while ((next != nullptr) && (next->priorityValue < node->priorityValue)) {
            prev = next;
            next = next->next;
        }
        prev->insert(node);
    }

private:
    NodeType m_head;
};

}

#endif
